# -*- coding: utf-8 -*-
# @Time    : 2021/1/5 上午10:45
# @Author  : tgy

"""
给定一个整型数组，代表数值不同的纸牌排成一条线。
玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿。
但是每个玩家每次只能拿走最左或者最右的纸牌，玩家A和B都绝顶聪明，请返回最后获胜者的分数。
"""


def first_puke(cards, start, end):
    ...
    if start == end:
        return cards[start]
    # 选 start
    start_val = cards[start] + second_puke(cards, start + 1, end)
    # 选 end
    end_val = cards[end] + second_puke(cards, start, end - 1)
    return max(start_val, end_val)


def second_puke(cards, start, end):
    # 由于是后选，start == end时，先选的把 start选了，这时没有可以选的，直接返回 0
    if start == end:
        return 0
    # 因为是后选，第一大的被选了，只能获取第二大的
    return min(first_puke(cards, start + 1, end), first_puke(cards, start, end - 1))


if __name__ == '__main__':
    ...
    cards = [1, 2, 100, 4]
    first_val = first_puke(cards, 0, len(cards) - 1)
    print(first_val)
    """
     后取
     如果A把 1取走了， 剩下 [100,4] 前取
    """
    second_val = second_puke(cards, 0, len(cards) - 1)
    print(second_val)
    # dp_first[i][j] = max(vals[i] + dp_second[i+1][j],vals[j] + dp_second[i][j - 1])

    # dp_second[i][j] = min(dp_first[i+1][j],dp_first[i][j - 1]);
